package advanced.class04;

import java.util.LinkedList;

/**
 * 左神进阶班第四课：计算字符串表达式
 */
public class Code_07_ExpressionCompute {

	// 主函数入口
	public static int getValue(String str) {
		return value(str.toCharArray(), 0)[0];
	}

	/**
	 *
	 * @param str  给定字符串的字符数组
	 * @param i    起始位置
	 * @return     返回值arr[0]表示当前的计算的结果，arr[1]表示结束位置
	 */
	public static int[] value(char[] str, int i) {
		LinkedList<String> que = new LinkedList<String>();
		int pre = 0;   // 用于存放int数值
		int[] bra = null;
		while (i < str.length && str[i] != ')') {  // 当前字符不为")"且没有遍历完时，只可能有下面三种情况
			// 1. 当前位置的元素是数组，累加求当前的数
			if (str[i] >= '0' && str[i] <= '9') {
				pre = pre * 10 + str[i++] - '0';
			} else if (str[i] != '(') {
				// 2. 如果当前的符号不是"("，那么只可能是加减乘除运算符，加入队列
				addNum(que, pre);
				que.addLast(String.valueOf(str[i++]));
				pre = 0;
			} else {
				// 当前位置是左“（”括号，拿球从此位置的下一个位置开始求解，直到遇到')'
				bra = value(str, i + 1);
				pre = bra[0];
				i = bra[1] + 1;
			}
		}
		// 将最后获取出来的pre加入到que中
		addNum(que, pre);
		return new int[] { getNum(que), i };   // 计算que的内容并返回
	}

	// 将数值num加入LinkedList中去
	public static void addNum(LinkedList<String> que, int num) {
		if (!que.isEmpty()) {
			int cur = 0;
			String top = que.pollLast();
			// 如果式加减，直接入栈，否则弹出计算结束之后再入栈
			if (top.equals("+") || top.equals("-")) {
				que.addLast(top);
			} else {
				cur = Integer.valueOf(que.pollLast());
				num = top.equals("*") ? (cur * num) : (cur / num);
		 	}
		}
		que.addLast(String.valueOf(num));
	}

	// 计算Que获取返回值
	public static int getNum(LinkedList<String> que) {
		int res = 0;
		boolean add = true;
		String cur = null;
		int num = 0;
		while (!que.isEmpty()) {
			cur = que.pollFirst();
			if (cur.equals("+")) {
				add = true;
			} else if (cur.equals("-")) {
				add = false;
			} else {
				num = Integer.valueOf(cur);
				res += add ? num : (-num);
			}
		}
		return res;
	}

	public static void main(String[] args) {
		String exp = "48*((70-65)-43)+8*1";
		System.out.println(getValue(exp));

		exp = "4*(6+78)+53-9/2+45*8";
		System.out.println(getValue(exp));

		exp = "10-5*3";
		System.out.println(getValue(exp));

		exp = "-3*4";
		System.out.println(getValue(exp));

		exp = "3+1*4";
		System.out.println(getValue(exp));

	}

}
